Hash tabela

Heš tabela (eng. Hash table) ili Heš mapa (eng. Hash map) je jedna struktura podataka koja koristi heš funkciju za učinkovito preslikavanje određenih ključeva u njima pridružene vrijednosti. Npr. imena ljudi u telefonske brojeve. Heš tabela se koristi za transformisanje ključa u indeks (heš), to jeste, mjesto u nizu elemenata gdje treba tražiti odgovarajuću vrijednost. Pošto je osnovna namjena heš tabele efikasan pristup podacima, ulazi heš tabele, pored ključeva, mogu da sadrže same zapise ili pokazivače na zapise koji su smješteni negdje drugo. Ovaj pristup je pogodniji sa stanovišta korištenja memorije, pogotovo ako su zapisi veći, jer kad bi se zapisi čuvali u samoj tabeli, mnogo prostora u praznim ulazima u rjeđe popunjenim tabelama bi ostalo neiskorišteno.

U najboljem slučaju, heš funkcija preslikava svaki mogući ključ u zaseban indeks, ali je to u praksi skoro nemoguće. Većina implementacija heš tabela podrazumijeva da su heš kolizije - parovi različitih ključeva s istim heš vrijednostima - obična pojava, i na neki način se brine da se ovaj problem savlada.

U dobro dimenzioniranoj heš tabeli, prosječna cijena (broj računarskih naredbi) svakog pronalaženja ne zavisi o broja elemenata koji se nalaze u tabeli. Mnoge implementacije heš tabela također omogućuju proizvoljna unošenja i brisanja parova ključeva i vrijednosti uz konstantnu prosječnu (amortiziranu) cijenu po operaciji. U mnogim okolnostima, hash tabele se pokazuju učinkovitijim od stabala pretrage ili drugih tabličnih struktura. Zato su hash tabele u širokoj upotrebi u svim vrstama računarskog softvera.